#include <iostream>
#include <queue>
using namespace std;
#define N 10005
#define INF 0x3f3f3f3f
// dis用于记录从起点到i的最短路,vis标记是否用过,f用于存储前驱到后驱的权值
int dis[N], vis[N], map[N][N];
int n,m,s;

// O(n2)版
void dijkstra_n2(int s){
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s] = 0;
    for(int i=1;i<=n;i++){
        int t=-1;//用于找第一个未被标记的点

        // 从 「未求出最短路径的点」中 取出「距离起点」最近的点
        for(int j=1;j<=n;j++)
            if(!vis[j]&&(t==-1||dis[j]<dis[t]))t=j;
        vis[t]=1; // 标记为已求出最短路径的点
        // 以这个点为桥梁 刷新「未求出最短路径的点」的距离
        for(int j=1;j<=n;j++)
            dis[j] = min(dis[j], dis[t]+map[t][j]);
    }
}

// 邻接表建图
// Next[i]，表示与第i条边起点相同的上一条边的编号。
// head[i]，表示以顶点i为起点的最后一条边的编号。一般初始化为-1
// val 边权，to 终点
int head[N],Next[N],val[N],to[N];
void add_edge(int u, int v, int w){
    static int cnt=0;
    to[++cnt]=v; val[cnt]=w; Next[cnt]=head[u]; head[u]=cnt;
}

struct Node{
    int d, x; //距离，当前点
    Node(int _d, int _x):d(_d),x(_x){};
    bool operator< (Node p) const{
        return d > p.d;
    }
};

// 堆优化O(mlogn)版
void dijkstra_mn(int s){
    memset(dis,INF,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue<Node> q;
    dis[s]=0;
    q.push(Node{dis[s],s});
    while(!q.empty()){
        Node tmp = q.top(); q.pop();
        int x = tmp.x;
        if(vis[x])continue;
        vis[x]=1;
        for(int i=head[x];i;i=Next[i]){
            int y = to[i]; 
            if(dis[y]>dis[x]+val[i]){
                dis[y] = dis[x]+val[i];
                q.push(Node{dis[y],y});
            }
        }
    }
}

int main(){
    cin>>n>>m>>s;
    int u,v,w;
    // 邻接矩阵建图+dijkstra_n2
    memset(map,INF,sizeof(map));
    for(int i=0;i<m;++i){
        cin>>u>>v>>w;
        map[u][v]=w;
    }
    dijkstra_n2(s);
    for(int i=1;i<=n;++i)cout<<dis[i]<<endl;

    // 邻接表建图+dijkstra_nm
    memset(head,-1,sizeof(head));
    for(int i=0;i<m;i++){
        cin>>u>>v>>w;
        add_edge(u,v,w);
    }
    dijkstra_mn(s);
    for(int i=1;i<=n;++i)cout<<dis[i]<<endl;
    return 0;
}